{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distance to a Cycle in Undirected Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distanceToCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无向图中到环的距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code>，表示一个 <strong>连通无向图</strong> 中的节点数，该图&nbsp;<strong>只包含一个&nbsp;</strong>环。节点编号为 <code>0</code> ~ <code>n - 1</code>(<strong>含</strong>)。</p>\n",
    "\n",
    "<p>你还得到了一个二维整数数组 <code>edges</code>，其中 <code>edges[i] = [node1<sub>i</sub>, node2<sub>i</sub>]</code> 表示有一条&nbsp;<strong>双向&nbsp;</strong>边连接图中的 <code>node1<sub>i</sub></code> 和 <code>node2<sub>i</sub></code>。</p>\n",
    "\n",
    "<p>两个节点 <code>a</code> 和 <code>b</code> 之间的距离定义为从 <code>a</code> 到 <code>b</code> 所需的&nbsp;<strong>最小边数</strong>。</p>\n",
    "\n",
    "<p>返回<em>一个长度为 <code>n</code> 的整数数组 <code>answer</code>，其中 </em><code>answer[i]</code><em> 是第 <code>i</code> 个节点与环中任何节点之间的最小距离</em>。</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/03/15/image-20220315154238-1.png\" style=\"width: 350px; height: 237px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]\n",
    "<strong>输出:</strong> [1,0,0,0,0,1,2]\n",
    "<strong>解释:</strong>\n",
    "节点 1, 2, 3, 和 4 来自环。\n",
    "0 到 1 的距离是 1。\n",
    "1 到 1 的距离是 0。\n",
    "2 到 2 的距离是 0。\n",
    "3 到 3 的距离是 0。\n",
    "4 到 4 的距离是 0。\n",
    "5 到 2 的距离是 1。\n",
    "6 到 2 的距离是 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/03/15/image-20220315154634-1.png\" style=\"width: 400px; height: 297px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]\n",
    "<strong>输出:</strong> [0,0,0,1,2,2,1,2,2]\n",
    "<strong>解释:</strong>\n",
    "节点 0, 1, 和 2 来自环.\n",
    "0 到 0 的距离是 0。\n",
    "1 到 1 的距离是 0。\n",
    "2 到 2 的距离是 0。\n",
    "3 到 1 的距离是 1。\n",
    "4 到 1 的距离是 2。\n",
    "5 到 1 的距离是 2。\n",
    "6 到 2 的距离是 1。\n",
    "7 到 2 的距离是 2。\n",
    "8 到 2 的距离是 2。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= node1<sub>i</sub>, node2<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>node1<sub>i</sub> != node2<sub>i</sub></code></li>\n",
    "\t<li>图是连通的。</li>\n",
    "\t<li>这个图只有一个环。</li>\n",
    "\t<li>任何顶点对之间最多只有一条边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distance-to-a-cycle-in-undirected-graph](https://leetcode.cn/problems/distance-to-a-cycle-in-undirected-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distance-to-a-cycle-in-undirected-graph](https://leetcode.cn/problems/distance-to-a-cycle-in-undirected-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]', '9\\n[[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]  # 反图\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "\n",
    "        # 拓扑排序后，deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 1)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:\n",
    "                    q.append(y)\n",
    "\n",
    "        ans = [0] * n\n",
    "        q = [i for i, d in enumerate(deg) if d >= 2]\n",
    "        vis = set(q)\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x in q:\n",
    "                ans[x] = cnt\n",
    "                for y in g[x]:\n",
    "                    if y not in vis:\n",
    "                        vis.add(y)\n",
    "                        nq.append(y)\n",
    "            q = nq\n",
    "            cnt += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 拓扑排序可以检测环\n",
    "        g = defaultdict(list)\n",
    "        inDegrees =[0] * n\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            inDegrees[a] += 1\n",
    "            inDegrees[b] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if inDegrees[i] == 1:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            curr = q.popleft()\n",
    "            res[curr] = -1\n",
    "            inDegrees[curr] -= 1\n",
    "            for nxt in g[curr]:\n",
    "                inDegrees[nxt] -= 1\n",
    "                if inDegrees[nxt] == 1:\n",
    "                    q.append(nxt)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if res[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            curr = q.popleft()\n",
    "            for nxt in g[curr]:\n",
    "                if res[nxt] != -1:\n",
    "                    continue\n",
    "                res[nxt] = res[curr] + 1\n",
    "                q.append(nxt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        rd=[0]*n\n",
    "        g=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            rd[x]+=1\n",
    "            rd[y]+=1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        q=[i for i in range(n) if rd[i]==1]\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for i in nq:\n",
    "                rd[i]-=1\n",
    "                for j in g[i]:\n",
    "                    rd[j]-=1\n",
    "                    if rd[j]==1:\n",
    "                        q.append(j)\n",
    "        res=[-1]*n\n",
    "        q=[]\n",
    "        for i in range(n):\n",
    "            if rd[i]==2:\n",
    "                res[i]=0\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for i in nq:\n",
    "                for j in g[i]:\n",
    "                    if res[j]==-1:\n",
    "                        res[j]=res[i]+1\n",
    "                        q.append(j)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        degree = [0 for _ in range(n)]\n",
    "        table = [set() for _ in range(n)]\n",
    "        for e in edges:\n",
    "            table[e[0]].add(e[1])\n",
    "            table[e[1]].add(e[0])\n",
    "            degree[e[0]] += 1\n",
    "            degree[e[1]] += 1\n",
    "        q = deque()\n",
    "        removed = [False for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:\n",
    "                q.append(i)\n",
    "                removed[i] = True\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            for y in table[now]:\n",
    "                if not removed[y]:\n",
    "                    degree[y] -= 1\n",
    "                    if degree[y] == 1:\n",
    "                        q.append(y)\n",
    "                        removed[y] = True\n",
    "        for i in range(n):\n",
    "            if not removed[i]:\n",
    "                q.append(i)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            for y in table[now]:\n",
    "                if removed[y]:\n",
    "                    ans[y] = ans[now] + 1\n",
    "                    q.append(y)\n",
    "                    removed[y] = False\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        vis=[0]*n\n",
    "        ind={i:0 for i in range(n)}\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "            ind[s]+=1\n",
    "            ind[e]+=1\n",
    "        stack=collections.deque()\n",
    "        for x in ind:\n",
    "            if ind[x]==1:\n",
    "                stack.append(x)\n",
    "        while stack:\n",
    "            cur=stack.popleft()\n",
    "            vis[cur]=-1\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex]==1:\n",
    "                    stack.append(nex)\n",
    "       # print(vis)\n",
    "       # print(ad)\n",
    "        for i in range(n):\n",
    "            if vis[i]==0:\n",
    "                stack=collections.deque()\n",
    "                stack.append([i,0])\n",
    "                while stack:\n",
    "                  #  print(cur,stack)\n",
    "                    cur,d =stack.popleft()\n",
    "                    for nex in ad[cur]:\n",
    "                        if vis[nex]==-1:\n",
    "                            vis[nex]=d+1\n",
    "                            stack.append([nex,d+1])\n",
    "        return vis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1)\n",
    "        f = [0] * n\n",
    "        seq = []\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            seq.append(i)\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                f[i] = j\n",
    "                if len(g[j]) == 1:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        ans = [0] * n\n",
    "        for i in seq[::-1]:\n",
    "            ans[i] = ans[f[i]] + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        m2 = defaultdict(set)\n",
    "        for i in edges:\n",
    "            m1[i[1]] += 1\n",
    "            m1[i[0]] += 1\n",
    "            m2[i[0]].add(i[1])\n",
    "            m2[i[1]].add(i[0])\n",
    "        collected = set()\n",
    "        todo = []\n",
    "        for i in m1:\n",
    "            if m1[i] == 1:\n",
    "                todo.append(i)\n",
    "            \n",
    "        while True:\n",
    "            if len(todo) == 0:\n",
    "                break\n",
    "            todo2 = []\n",
    "            for i in todo:\n",
    "                for x in m2[i]:\n",
    "                    m1[x] -= 1\n",
    "                    if m1[x] == 1:\n",
    "                        todo2.append(x)\n",
    "                del m1[i]\n",
    "                collected.add(i)\n",
    "            todo = todo2\n",
    "\n",
    "        ret = [0]*n\n",
    "        dq = deque()\n",
    "        for i in range(n):\n",
    "            if i in collected:\n",
    "                ret[i] = 0\n",
    "            else:\n",
    "                dq.append((i, 0))\n",
    "        used = set()\n",
    "        while dq:\n",
    "            first, step = dq.popleft()\n",
    "            if first in used:\n",
    "                continue\n",
    "            used.add(first)\n",
    "            ret[first] = step\n",
    "            for i in m2[first]:\n",
    "                if i not in collected:\n",
    "                    dq.append((i, 0))\n",
    "                else:\n",
    "                    dq.append((i, step+1))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, directed: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - directed: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    deg = [0] * n\n",
    "    if directed:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                if u < v:\n",
    "                    deg[u] += 1\n",
    "                    deg[v] += 1\n",
    "\n",
    "    startDeg = 0 if directed else 1\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    depth = [0] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"从基环出发，求所有树枝上的点的深度.\"\"\"\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            adjList[u].append(v)\n",
    "            adjList[v].append(u)\n",
    "        cycles, *_ = cyclePartition(n, adjList, directed=False)\n",
    "\n",
    "        def bfsMultiStart(starts: Sequence[int], adjList: List[List[int]]) -> List[int]:\n",
    "            \"\"\"多源bfs\"\"\"\n",
    "            n = len(adjList)\n",
    "            dist = [int(1e18)] * n\n",
    "            queue = deque(starts)\n",
    "            for start in starts:\n",
    "                dist[start] = 0\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for next in adjList[cur]:\n",
    "                    cand = dist[cur] + 1\n",
    "                    if cand < dist[next]:\n",
    "                        dist[next] = cand\n",
    "                        queue.append(next)\n",
    "            return dist\n",
    "\n",
    "        return bfsMultiStart(cycles[0], adjList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "INF=int(1e18)\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, directed: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - directed: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    deg = [0] * n\n",
    "    if directed:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                if u < v:\n",
    "                    deg[u] += 1\n",
    "                    deg[v] += 1\n",
    "\n",
    "    startDeg = 0 if directed else 1\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    depth = [0] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"从基环出发，求所有树枝上的点的深度.\"\"\"\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            adjList[u].append(v)\n",
    "            adjList[v].append(u)\n",
    "        cycles, *_ = cyclePartition(n, adjList, directed=False)\n",
    "\n",
    "        def bfsMultiStart(starts: Sequence[int], adjList: List[List[int]]) -> List[int]:\n",
    "            \"\"\"多源bfs\"\"\"\n",
    "            n = len(adjList)\n",
    "            dist = [INF] * n\n",
    "            queue = deque(starts)\n",
    "            for start in starts:\n",
    "                dist[start] = 0\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for next in adjList[cur]:\n",
    "                    cand = dist[cur] + 1\n",
    "                    if cand < dist[next]:\n",
    "                        dist[next] = cand\n",
    "                        queue.append(next)\n",
    "            return dist\n",
    "\n",
    "        return bfsMultiStart(cycles[0], adjList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [-1] * n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        def dfs(u: int, par: int) -> None:\n",
    "            if parent[u] < 0:\n",
    "                parent[u] = par\n",
    "                for v in graph[u]:\n",
    "                    if v > 0 and v != par:\n",
    "                        dfs(v, u)\n",
    "\n",
    "        def pathTo(u: int) -> List[int]:\n",
    "            ans = []\n",
    "            while u >= 0:\n",
    "                ans.append(u)\n",
    "                u = parent[u]\n",
    "            return ans\n",
    "\n",
    "        def findCycle(u: int, v: int) -> List[int]:\n",
    "            pu = pathTo(u)\n",
    "            pv = pathTo(v)\n",
    "            last = -1\n",
    "            while pu and pv and pu[-1] == pv[-1]:\n",
    "                last = pu.pop()\n",
    "                pv.pop()\n",
    "            pu.extend(pv)\n",
    "            pu.append(last)\n",
    "            return pu\n",
    "\n",
    "        def bfs(u: int, v: int) -> List[int]:\n",
    "            que = collections.deque(findCycle(u, v))\n",
    "            seen = [False] * n\n",
    "            for i in que:\n",
    "                seen[i] = True\n",
    "            ans = [0] * n\n",
    "            lev = 0\n",
    "\n",
    "            while que:\n",
    "                sz = len(que)\n",
    "                for _ in range(sz):\n",
    "                    cur = que.popleft()\n",
    "                    ans[cur] = lev\n",
    "                    for i in graph[cur]:\n",
    "                        if not seen[i]:\n",
    "                            que.append(i)\n",
    "                            seen[i] = True\n",
    "                lev += 1\n",
    "\n",
    "            return ans\n",
    "\n",
    "        dfs(0, -1)\n",
    "        redundant = next(e for e in edges if parent[e[0]] != e[1] and parent[e[1]] != e[0])\n",
    "        return bfs(redundant[0], redundant[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n,self.adjMap)\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue = deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int,adjMap:DefaultDict[int,Set[int]])->List[int]:\n",
    "        res = []\n",
    "        self.path = []\n",
    "        self.visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path = [i]\n",
    "            if self.dfs(i, -1):\n",
    "                break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1] != last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,u:int,pre:int)->bool:   #环检测，并记录路径\n",
    "        if self.visited[u]:return True\n",
    "        self.visited[u]=True\n",
    "        for v in self.adj[u]:       #存在(u,v)边\n",
    "            if v==pre:continue      #跳过(u,v,u)的环\n",
    "            self.path.append(v)\n",
    "            if self.dfs(v,u):return True\n",
    "            self.path.pop()         #回溯\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        cycle=[]\n",
    "        self.path=[]\n",
    "        self.visited=[False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        cycle.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            cycle.append(self.path.pop())\n",
    "        return cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while qu:\n",
    "            length=len(qu)\n",
    "            for _ in range(length):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        queue=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        queue.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,u:int,pre:int)->bool:   #环检测，并记录路径\n",
    "        if self.visited[u]:return True\n",
    "        self.visited[u]=True\n",
    "        for v in self.adj[u]:\n",
    "            if v==pre:continue\n",
    "            self.path.append(v)\n",
    "            if self.dfs(v,u):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:   #环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adj[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        res=[n+1]*n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist+=1\n",
    "        return res\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,u:int,pre:int)->bool:   #环检测，并记录路径\n",
    "        if self.visited[u]:return True\n",
    "        self.visited[u]=True\n",
    "        for v in self.adj[u]:       #存在(u,v)边\n",
    "            if v==pre:continue      #跳过(u,v,u)的环\n",
    "            self.path.append(v)\n",
    "            if self.dfs(v,u):return True\n",
    "            self.path.pop()         #回溯\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        cycle=[]                    #存放环上的顶点\n",
    "        self.path=[]\n",
    "        self.visited=[False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            #self.path=[i]\n",
    "            self.path.append(i)\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        cycle.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            cycle.append(self.path.pop())\n",
    "        return cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        res=[int(1e20)]*n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist+=1\n",
    "        return res\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        def dfs(cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "            if self.visited[cur]: return True\n",
    "            self.visited[cur]=True\n",
    "            for next in adjMap[cur]:\n",
    "                if next == pre:continue\n",
    "                self.path.append(next)\n",
    "                if dfs(next, cur):\n",
    "                    return True\n",
    "                self.path.pop()\n",
    "            return False\n",
    "\n",
    "        def findCycle(n: int, adjMap: DefaultDict[int, Set[int]]) -> List[int]:\n",
    "            res = []\n",
    "            self.path = []\n",
    "            self.visited = [False] * n\n",
    "            for i in range(n):\n",
    "                if self.visited[i]:continue\n",
    "                self.path = [i]\n",
    "                if dfs(i, -1):\n",
    "                    break\n",
    "            last=self.path.pop()\n",
    "            res.append(last)\n",
    "            while self.path and self.path[-1] != last:\n",
    "                res.append(self.path.pop())\n",
    "            return res\n",
    "\n",
    "        \"\"\"无向图中恰有一个环\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "        cycle = findCycle(n, adjMap)\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue = deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,u:int,pre:int)->bool:   #环检测，并记录路径\n",
    "        if self.visited[u]:return True\n",
    "        self.visited[u]=True\n",
    "        for v in self.adj[u]:       #存在(u,v)边\n",
    "            if v==pre:continue      #跳过(u,v,u)的环\n",
    "            self.path.append(v)\n",
    "            if self.dfs(v,u):return True\n",
    "            self.path.pop()         #回溯\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        cycle=[]                    #存放环上的顶点\n",
    "        self.path=[]\n",
    "        self.visited=[False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        cycle.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            cycle.append(self.path.pop())\n",
    "        return cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        ans=[n+1]*n\n",
    "        for i in cycle:\n",
    "            ans[i]=0\n",
    "        qu=deque([i for i in cycle])\t#全部顶点进队\n",
    "        dist=0\n",
    "        while qu:                   #队不空循环\n",
    "            cnt=len(qu)\n",
    "            for i in range(0,cnt):\n",
    "                cur=qu.popleft()\n",
    "                for next in self.adj[cur]:\n",
    "                    if ans[next]>dist+1:\n",
    "                        ans[next]=dist+1\n",
    "                        qu.append(next)\n",
    "            dist+=1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self,u:int,pre:int)->bool:   #环检测，并记录路径\n",
    "        if self.visited[u]:return True\n",
    "        self.visited[u]=True\n",
    "        for v in self.adj[u]:       #存在(u,v)边\n",
    "            if v==pre:continue      #跳过(u,v,u)的环\n",
    "            self.path.append(v)\n",
    "            if self.dfs(v,u):return True\n",
    "            self.path.pop()         #回溯\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        cycle=[]                    #存放环上的顶点\n",
    "        self.path=[]\n",
    "        self.visited=[False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path.append(i)\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        cycle.append(last)\n",
    "        while len(self.path)>0 and self.path[-1]!=last:\n",
    "            cycle.append(self.path.pop())\n",
    "        return cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from collections import defaultdict, deque\n",
    "#from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        self.adjMap=defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            self.adjMap[u].add(v)\n",
    "            self.adjMap[v].add(u)\n",
    "        cycle=self.findCycle(n)\n",
    "        res=[n+1]*n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue=deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in self.adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist+=1\n",
    "        return res\n",
    "\n",
    "    def dfs(self,cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "        if self.visited[cur]: return True\n",
    "        self.visited[cur]=True\n",
    "        for next in self.adjMap[cur]:\n",
    "            if next == pre:continue\n",
    "            self.path.append(next)\n",
    "            if self.dfs(next,cur):\n",
    "                return True\n",
    "            self.path.pop()\n",
    "        return False\n",
    "\n",
    "    def findCycle(self,n:int)->List[int]:\n",
    "        res=[]\n",
    "        self.path = []\n",
    "        self.visited = [False]*n\n",
    "        for i in range(n):\n",
    "            if self.visited[i]:continue\n",
    "            self.path=[i]\n",
    "            if self.dfs(i,-1):break\n",
    "        last=self.path.pop()\n",
    "        res.append(last)\n",
    "        while self.path and self.path[-1]!=last:\n",
    "            res.append(self.path.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        def findCycle(n: int, adjMap: DefaultDict[int, Set[int]]) -> List[int]:\n",
    "            def dfs(cur: int, pre: int) -> bool:\t#环检测，并记录路径\n",
    "                if visited[cur]: return True\n",
    "                visited[cur] = True\n",
    "                for next in adjMap[cur]:\n",
    "                    if next == pre:continue\n",
    "                    path.append(next)\n",
    "                    if dfs(next, cur):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                return False\n",
    "\n",
    "            res = []\n",
    "            path = []\n",
    "            visited = [False] * n\n",
    "            for i in range(n):\n",
    "                if visited[i]:continue\n",
    "                path = [i]\n",
    "                if dfs(i, -1):\n",
    "                    break\n",
    "            last = path.pop()\n",
    "            res.append(last)\n",
    "            while path and path[-1] != last:\n",
    "                res.append(path.pop())\n",
    "            return res\n",
    "\n",
    "        \"\"\"无向图中恰有一个环\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "        cycle = findCycle(n, adjMap)\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "        queue = deque([i for i in cycle])\n",
    "        dist=0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        def findCycle(n: int, adjMap: DefaultDict[int, Set[int]]) -> List[int]:\n",
    "            def dfs(cur: int, pre: int) -> bool:\n",
    "                \"\"\"环检测，并记录路径\"\"\"\n",
    "                if visited[cur]:\n",
    "                    return True\n",
    "                visited[cur] = True\n",
    "                for next in adjMap[cur]:\n",
    "                    if next == pre:\n",
    "                        continue\n",
    "                    path.append(next)\n",
    "                    if dfs(next, cur):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                return False\n",
    "\n",
    "            res = []\n",
    "            path = []\n",
    "            visited = [False] * n\n",
    "\n",
    "            for i in range(n):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                path = [i]\n",
    "                if dfs(i, -1):\n",
    "                    break\n",
    "\n",
    "            last = path.pop()\n",
    "            res.append(last)\n",
    "            while path and path[-1] != last:\n",
    "                res.append(path.pop())\n",
    "\n",
    "            return res\n",
    "\n",
    "        \"\"\"无向图中恰有一个环\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "\n",
    "        cycle = findCycle(n, adjMap)\n",
    "\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "\n",
    "        queue = deque([i for i in cycle])\n",
    "        dist = 0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set\n",
    "\n",
    "class Solution:\n",
    "    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        def findCycle(n: int, adjMap: DefaultDict[int, Set[int]]) -> List[int]:\n",
    "            def dfs(cur: int, pre: int) -> bool:\n",
    "                \"\"\"环检测，并记录路径\"\"\"\n",
    "                if visited[cur]:\n",
    "                    return True\n",
    "                visited[cur] = True\n",
    "                for next in adjMap[cur]:\n",
    "                    if next == pre:\n",
    "                        continue\n",
    "                    path.append(next)\n",
    "                    if dfs(next, cur):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                return False\n",
    "\n",
    "            res = []\n",
    "            path = []\n",
    "            visited = [False] * n\n",
    "\n",
    "            for i in range(n):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                path = [i]\n",
    "                if dfs(i, -1):\n",
    "                    break\n",
    "\n",
    "            last = path.pop()\n",
    "            res.append(last)\n",
    "            while path and path[-1] != last:\n",
    "                res.append(path.pop())\n",
    "\n",
    "            return res\n",
    "\n",
    "        \"\"\"无向图中恰有一个环\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "\n",
    "        cycle = findCycle(n, adjMap)\n",
    "\n",
    "        res = [int(1e20)] * n\n",
    "        for index in cycle:\n",
    "            res[index] = 0\n",
    "\n",
    "        queue = deque([i for i in cycle])\n",
    "        dist = 0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if res[next] > dist + 1:\n",
    "                        res[next] = dist + 1\n",
    "                        queue.append(next)\n",
    "            dist += 1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
